package pers.sloera.leetcode.uniquePaths;

import java.time.Duration;
import java.time.Instant;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 62. 不同路径
 * <p>
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * <p>
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * <p>
 * 问总共有多少条不同的路径？
 *
 * @author SloeraN
 * @version 1.0
 * @class pers.sloera.leetcode.uniquePaths.Solution
 * @date 2020/12/9
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Instant now = Instant.now();
        int i = solution.uniquePaths(51, 9);
        System.out.println(i);
        System.out.println(Duration.between(now, Instant.now()).toMillis());
    }

    /**
     * 缓存key 的分隔符
     */
    private final static String KEY_SEPARATE = ",";

    /**
     * 思路
     * 从(0,0)到(m,n)即为：(0,1)到(m,n) + (1,0)到(m,n)，可将(0,1)与(1,0)看作新的起始点，演变为递归问题。
     * <p>
     * 边界条件为：到达下/右边界。右边界：只能继续往下走；下边界：只能继续往右走。
     * <p>
     * 优化
     * 为避免超时，引入一个map用于缓存。将起始的横纵值做为map的key，此点到终点的路径为做为值。在递归查询前先查询此map，已有值直接使用，无值加入做为缓存。
     *
     * @param m 行数
     * @param n 列数
     * @return int
     * @date 2020/12/9
     */
    public int uniquePaths(int m, int n) {
        int result = 0;
        HashMap<String, Integer> cache = new HashMap<>();
        result += findPaths(0, 0, n - 1, m - 1, cache);
        return result;
    }

    /**
     * 递归(startX,startY)到(endX, endY)的路径
     *
     * @param startX 起始横坐标
     * @param startY 起始纵坐标
     * @param endX 结束横坐标
     * @param endY 结束纵坐标
     * @param cache 路径缓存
     * @return 查找到的路径数
     */
    private int findPaths(int startX, int startY, int endX, int endY, Map<String, Integer> cache) {
        int result = 0;
        // 到右边界
        if (startX >= endX) {
            result++;
            return result;
        }
        // 到左边界
        if (startY >= endY) {
            result++;
            return result;
        }
        // 右移
        int pathRight;
        if (Objects.nonNull(cache.get((startX + 1) + KEY_SEPARATE + startY))) {
            pathRight = cache.get((startX + 1) + KEY_SEPARATE + startY);
        } else {
            pathRight = findPaths(startX + 1, startY, endX, endY, cache);
            cache.put((startX + 1) + KEY_SEPARATE + startY, pathRight);
        }
        result += pathRight;
        // 下移
        int pathDown;
        if (Objects.nonNull(cache.get(startX + KEY_SEPARATE + (startY + 1)))) {
            pathDown = cache.get(startX + KEY_SEPARATE + (startY + 1));
        } else {
            pathDown = findPaths(startX, (startY + 1), endX, endY, cache);
            cache.put(startX + KEY_SEPARATE + (startY + 1), pathDown);
        }
        result += pathDown;
        return result;
    }
}
